package cxydmmszl.chapter02.t024;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashSet;
import java.util.Set;

/**
 * <li style="color: red;">Prob</li>
 * 删除无序链表中值重复出现的节点
 * <li style="color: green;">Desc</li>
 * 给定一个无序链表，删除其中值重复出现的节点（保留当中顺序遍历第一个出现的节点）。
 * <li style="color: green;">Input</li>
 * 第一行一个整数 n，表示单链表的节点数量。
 * 第二行 n 个整数表示单链表的节点的值。
 * <li style="color: green;">Output</li>
 * 顺序输出单链表每个节点的值。
 * <li style="color: blue;">Link</li> CD137
 *
 * @author habitplus
 * @since 2021-09-10 13:28
 */
public class Main {
    private static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    private static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            e.printStackTrace();
        }
        return 0;
    }

    private static class Node {
        int val;
        Node next;
        public Node(int val) {
            this.val = val;
        }
    }

    private static Node readAndGenList(int n) {
        Node tou = new Node(0), pre = tou, node;
        int num;
        for (int i = 0; i < n; i++) {
            num = nextInt();
            node = new Node(num);
            pre.next = node;
            pre = node;
        }

        return tou.next;
    }

    private static void printLinkedList(Node head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val).append(" ");
            head = head.next;
        }
        System.out.println(sb.toString());
    }

    public static Node delRepeatNodes1(Node head) {
        if (head == null || head.next == null){
            return head;
        }

        Set<Integer> set = new HashSet<>();

        Node tou = new Node(0);
        tou.next = head;
        Node pre = tou;

        while (head != null) {
            if (set.contains(head.val)) {
                // 删除当前节点
                pre.next = head.next;
            } else {
                set.add(head.val);
                pre = head;
            }
            head = head.next;
        }
        return tou.next;
    }

    public static Node delRepeatNodes2(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node cur = head;
        Node pre, nxt;

        while (cur != null) {
            pre = cur;
            nxt = cur.next;
            while (nxt != null) {
                if (cur.val == nxt.val) {
                    // 删除该节点
                    pre.next = nxt.next;
                } else {
                    pre = nxt;
                }
                nxt = nxt.next;
            }
            cur = cur.next;
        }

        return head;
    }

    public static void main(String[] args) {
        int n = nextInt();
        Node head = readAndGenList(n);

        head = delRepeatNodes1(head);
        printLinkedList(head);
    }
}
